1.4 Quantum complexity
在Shor之前，已经有人对量子计算跃跃欲试。“量子系统可以用来执行计算”这个想法分别由Paul Benioff和Richard Feynman在1982年独立提出。这个想法随着微型电路的小型化而自然产生，因为到很小尺度，量子效应必然显著，Benioff就基于这个想法。但是Feynman的出发点很不一样，要了解Feynman的洞见，先得说说量子信息和量子计算的数学描述。
传统比特(bit)最小的不可分单元用0和1两种状态表示，而量子比特(qubit)用归一正交基 和两个态张成的二维复空间表示。一个归一化的量子比特表示为，其中，且。我们可以测量到两个基的投影大小。测量结果是不确定的：测量结果是态的概率是，态的概率是。
N个qubits构成的量子态可以用维希尔伯特空间的向量表示，比如。如果每一个维正交归一基被编号为，那么我们就可以定义这个空间里的一般状态，其中。如果我们在每一个qubit位上都用投影到正交基的测量方法来测量N个qubits，那么得到态的概率为。
现在可以开始讨论量子计算了。我们制备具有N个qubits的标准初态，或表示成。然后对这个初态做幺正变换（可分解成标准化量子逻辑门的乘积，每个标准量子门每次只对几个qubits做幺正变换）。幺正变换完成后，测量所有qubits在基向量上的投影，这个测量值就是计算的输出结果，所以最终的输出结果是可以打印在纸上的经典信息。
我们注意到，量子算法是一种概率算法(probabilistic algorithm)，即由于量子测量过程的随机性，同样的程序可能得到不同的输出，最终得到的是所有可能输出的一个分布函数。实际上，Shor的因数分解算法也只能保证大概率能得到正确的质因数；当然这也可接受，因为很容易验证结果是否正确。
需要说明的是，尽管物理原理不同，量子计算机可以计算的，经典计算机也都能计算。经典计算机可以储存和旋转向量，也可以模拟量子测量过程（投影到正交基向量）。因此，经典计算机能够以任意精度模拟量子计算机。用哪种计算机其实不是重点，因为什么问题是“可计算的”对两者来说是相同的。
但用经典计算机模拟量子计算机也有局限，需要考虑到这种模拟的时长。比如模拟qubits的量子计算机，表示任意一个一般的状态就需要用到个复数，这个存储能力已经远超任何经典计算机了，而且对维向量进行旋转操作也远超任何经典计算机的计算能力。相比之下，用经典比特表示的任意一个一般状态，尽管它同样可以表示个可能的状态，但只需要用长度为的二进制字符串描述即可。这样的话，纵使经典计算机可以模拟量子计算机，当变大的时候，用经典模拟量子也会无能为力，因为希尔伯特空间是在太大了！Feynman正是基于此才考虑到，量子计算机或许可以执行经典计算机不可能完成的任务（当然，量子计算机也可以轻而易举地模拟它自身！）。Shor的结果似乎印证了这个观点。
我们可以避免这个经典计算机能力的困境吗？反过来思考一下，我们只要求模拟能给所有可能的输出结果分配一个概率分布，但是中间过程不必完整模拟N-qubit的量子态演化过程。因此，我们可以设计一种经典算法的概率化版本(probabilistic classical algorithm)：输入并不唯一决定输出，而是输出结果服从与量子计算结果相同的概率分布。这是一种局域的模拟（local simulation）：每一步中，每个qubit有确定值，但处理这个qubit的量子逻辑门依据（伪）随机数选定所有可能的操作方式之一。这种模拟方式大大简化了完全跟踪量子态演化的方式。
但Bell不等式用数学定理不可辩驳地指出，经典算法的概率化模拟不可能实现：不存在局域概率化（local probabilistic algorithm）算法可以复现量子力学的结果！（译者注：量子关联是非局域的，即隐变量理论是不正确的。）因此，尽管没有已知的证明，但是用经典计算机模拟量子计算机似乎是很困难的。
为了理解为何量子信息的数学描述如此复杂，我们可以想象一个3N （）个qubits的量子系统，它被分为三个子系统，每个子系统各自有个qubits，分别叫做子系统(1)，(2)和(3)。我们随机选取一个3N qubits的量子态，然后把这三个子系统分开，把(1)发送到Santa Barbara，把(3)发送到San Diego，把(2)留在Pasadena。现在我们想通过测量来尽可能多地找出系统的信息。为了简单起见，假设我们手上有无数份原系统的拷贝，数量足够多，让我们可以测量任何想知道的可观测量注。除了一项限制条款：我们每次测量只能作用于其中一个子系统，不允许有跨越子系统边界的集体测量。于是，对于一个3N qubit典型的量子系统来说，我们的测量几乎得不到任何关于该量子态的有用信息。几乎所有用来区分不同量子态的信息都在子系统(1)、(2)、(3)测量结果的非局域关联（nonlocal correlations）中。这些关联就是Bell发现的用物理来描述量子信息所必须的非局域关联性。
信息量可以用熵来表征：熵越大表示信息越少。Don Page发现，如果我们随机从3N qubits中选择一个态，那么总会发现它每个子系统的熵非常接近 此处N是子系统熵的最大可能取值，对应于该子系统不携带任何信息。于是，对于N很大的情况，如果我们只分开测量每个子系统的话，只能得到指数级小量的信息。
也就是说，如果我们不考虑San Diego，Pasadena和Santa Barbara的测量结果之间是如何关联的话，我们的测量只能提供很少的信息。此处，“对于关联的测量”表示集体测量（collective measurement），即使它实际上可以是由不同的人对同一份拷贝的不同子系统各自做测量，然后打电话互相通知测量结果。通过测量关联，我们可以知道更多；原理上，我们可以完全重建出这个量子态。
任何一个关于3N qubits量子态的描述都必须把这些非局域的关联表征出来，然而这是非常复杂的一件事。这也是为何用经典模拟一个大的量子系统需要巨量计算资源的原因。当系统的不同部分之间存在这种非局域的关联时，我们称这些不同部分彼此“纠缠”（entangled），它表示我们不能通过简单地把系统分开单独研究每个部分，来获得整体的状态信息。
注. 我们无法对自己手上未知的量子态进行拷贝（量子不可克隆原理），但我们可以让另一个人制备好这些拷贝（他是可以做到的，因为他明确地知道这个态是什么），只要不告诉我们这个态就可以了。 ↩